1. Field of the Invention
This invention relates to improving the performance of matrix evaluations. The invention is also related to an improvement in performance in evaluating sparse matrices having at least one model containing information for at least one node in the matrix being evaluated. The invention is still further related to an improvement in the performance of matrix evaluations where the sparse matrix represents Kirchoff's voltage and current laws for an electronic circuit being evaluated, and where the models represent specific structures and contain at least one conductance contribution value of an electronic circuit component of the electronic circuit.
2. Discussion of the Background
The use of matrix based solvers (matrix solutions) to simulate transient behavior of electronic circuits dates back to 1 975, and is in wide use in the electronic design community. Nagel, L., SPICE 2: A Computer Program to Simulate Semiconductor Circuits, ERL Memo UCB/ERL M75/520, University of California, Berkeley, May 1975, hereinafter, SPICE; see also Cohen, E., Program Reference for SPICE 2, ERL, University of California, Berkeley, June 1976, hereinafter Cohen, and Quarles, T., Analysis of Performance and Convergence Issues for Circuit Simulation, EECS, University of California, Berkeley, April 1989, hereinafter, Quarles. This method of solution relies on the fact that differential circuit equations that describe transient behavior of circuits can be written as conductance coefficients (G) into a matrix, and the matrix can be solved to obtain new voltage values at each node of the circuit.
The use of matrix solutions has relied on a number of techniques to improve solution performance. Starting with SPICE, sparse matrix techniques have been utilized to reduce the amount of memory required to store the entire matrix. While sparse matrix systems reduce the amount of memory needed, they require a trade-off in performance due to the fact that the location of an individual matrix entry must be stored and because the matrix solution cannot be calculated through simple matrix index mathematics as in non-sparse systems.
FIG. 1A is a circuit diagram of a two resistor circuit (R.sub.1 and R.sub.2) having three circuit nodes (N.sub.1, N.sub.2, and N.sub.3). FIG. 1B is a matrix representing conductance values (G) of the two resistor circuit. The matrix element labeled G.sub.1 +G.sub.2 represents the circuit equation coefficients for the node N.sub.2 between the resistors.
In a single processor computer, matrix evaluation cycles proceed according to the flow diagram in FIG. 2. For each time point in the simulation, all of the device models are evaluated and the result is added to the matrix entry in a serial fashion. At Step 20, a model is evaluated. Such model can be, for example, a model representing resistor R.sub.1 in FIG. 1A. The model evaluation determines the conductance values (G) of the circuit element, resistor R.sub.1. At Step 22, the matrix is loaded with the conductance values determined in the model evaluation Step 20. In this example, the conductance values of the circuit element resistor R, is collectively referred to as a matrix stamp R, is inserted into the matrix (see Matrix stamp of R.sub.1, FIG. 1B). Steps 20 and 22 are repeated for each model to be evaluated.
At Step 24, the matrix is solved to determine voltage values at each node of the circuit. At Step 26, a convergence test is utilized to determine whether or not the circuit has reached a steady state solution. An example convergence test compares values at a vector of new nodal voltages (X.sub.i) to values from a last convergent time point (X.sub.i-1), and is defined as: EQU X.sub.i -X.sub.i-1 .ltoreq.Abstol+Reltol*Max(X.sub.i, X.sub.i-1),
where Astol and Reltol are user defined convergence control variables of the simulator (having default values of 1e-6 and 1e-3 respectively), and the function Max() returns the largest of two values.
If the convergence test does not reach steady state, the entire process is repeated for another simulated time point. In the above process, because the model evaluation can occupy as much as 50 percent of the processor's time, this leads to extremely long runs in large circuit simulation can be experienced.
The conventional implementation of matrix solvers has relied on device model structures similar to Resistor Model Structure 30 shown in FIG. 3. Resistor Model Structure 30 stores identifying information 32, including an instance and model identifier, and the conductance value G 36, as evaluated during model evaluation (Step 20 in FIG. 2, for example). In addition, Resistor Model Structure 30 stores the memory locations of the matrix entries (Pointers 38, for example). This mechanism requires that after each device model is evaluated, the new values of G (36, for example) must be `stamped` into the matrix during the matrix load phase. In a multiple processor system, each evaluation of a device model can be handed to a separate processor. As shown in FIG. 4, model evaluations 40a, 40b, and 40c are processed in parallel. While this can lead to some improvement in simulation time, the overall performance of the system will not be improved dramatically due to the nature of shared memory systems. Shared memory is utilized because some circuit equations cause overlapping entries at matrix positions where two or more circuit elements meet to form a circuit node, therefore the effect of adding additional processors is reduced because of a time consuming, serial process of matrix load (Step 42).
If each device model is evaluated by a separate processor, then the simulation can enter a situation known as a blocking memory write in which two (or more) processors attempt to write to the same memory location. This can be seen by referring to the matrix entry labeled G1+G2 in FIG. 1B and corresponding to node N.sub.2 in FIG. 1A, which shows that the value of this element has conductance contributions G.sub.1 and G.sub.2 from resistors R.sub.1 and R.sub.2, respectively.
Some mechanism must be provided to prevent two processors from writing to a given memory location simultaneously. A blocking memory write prevents simultaneous writes by locking a memory location (matrix entry), reading it's value, adding the evaluation of the other models (conductances) that contribute to this nodal voltage, and then unlocking the memory location. However, blocking memory writes are expensive due to the fact that all other processes that are contributing to the value at the memory location being written are blocked until the lock/unlock cycle completes. Furthermore, in order to avoid an enormous number of memory location lock operations and associated bookkeeping and memory consumption involved in managing those locks, multi-processing systems have historically locked and unlocked the entire matrix before and after each stamping step.
Bischoff and Greenburg's original method Bischoff, G., and Greenburg, S., Cayenne--A Parallel Implementation of the Circuit Simulator SPICE, Digital Equipment Corporation, Hudson Mass., CH2353-1/86/0000/0182.COPYRGT. 1986 IEEE, hereinafter Bischoff and Greenburg, overcomes this blocking problem by changing the matrix entry from a single scalar value to a sum value and a vector of individual conductances. As shown in FIG. 5, each matrix position (50, for example) includes a vector 52 where each vector entry (G2, for example) is a collection point for a single model evaluation. Thus, if two device models are connected to a circuit node, that node is represented in the matrix as a matrix position having three values, two of which provide locations for non-blocking writes by separate model evaluation processes (vector 52), and one of which is a sum value 54.
The effect of Bischoff and Greenburg's method on the matrix evaluation loop is shown in FIG. 6. Model evaluations 40a, 40b, and 40c are performed as before, however, matrix loads shown as matrix load 62a, 62b and 62c are now performed in parallel. Each matrix load performs stamping, via nonblocking writes, of individual conductance values from individual circuit elements into a single matrix position (vector entry). Steps 64a, 64b and 64c represent the summing of the sum values at each matrix position (sum value 54, FIG. 5, for example).
Bischoff and Greenburg's method provides an improvement in evaluation time of circuit simulations. However, because of the complexity of most circuits being evaluated, significant computational time is still required.